package de.unibi.comet.fa;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.TreeMap;

import de.unibi.comet.util.BitArray;
import de.unibi.comet.util.Log;

public class DFAFactory {
	
	public static CDFA build(Alphabet alphabet, List<GeneralizedString> l) {
		return build(alphabet, l, Integer.MAX_VALUE);
	}
	
	public static CDFA build(Alphabet alphabet, List<GeneralizedString> l, int nodeLimit) {
		Log.getInstance().startTimer();
		// positions in the bitarray where the patterns start/end
		int[] patternStarts = new int[l.size()];
		int[] patternEnds = new int[l.size()];
		int stringNr = 0;
		int position = 0;
		for (GeneralizedString s : l) {
			patternStarts[stringNr]=position;
			position+=s.length()+1;
			patternEnds[stringNr]=position-1;
			++stringNr;
		}
		int totalLength = position;
		BitArray startStates = new BitArray(totalLength);
		for (int i : patternStarts) startStates.set(i, true);
		// contains for each character the possible transitions
		// transions['a'].get(patternIndex[pattern no.]+i) = true means that transition 
		// from state i to state i+1 is possible when an 'a' was read
		// for given pattern no.
		BitArray[] transitions = new BitArray[alphabet.size()];
		for (int i=0; i<alphabet.size(); ++i) transitions[i] = new BitArray(totalLength);
		BitArray state = new BitArray(startStates);
		// build transitions table (nfa)
		stringNr=0;
		for (GeneralizedString s : l) {
			int offset = patternStarts[stringNr];
			for (int j=0; j<s.length(); ++j) {
				BitArray ba = s.getPosition(j);
				int character=0;
				for (boolean transitionPossible : ba) {
					if (transitionPossible) {
						transitions[character].set(offset+j,true);
					}
					++character;
				}
			}
			++stringNr;
		}
		// now construct DFA recursively
		TreeMap<BitArray, Integer> dfaNodes = new TreeMap<BitArray, Integer>();
		ArrayList<int[]> transitionTable = new ArrayList<int[]>(512);
		ArrayList<Integer> outputTable = new ArrayList<Integer>(512);
		
		// states still to be build along with their subsets
		Stack<Integer> toBuild = new Stack<Integer>(); 
		Stack<BitArray> toBuildSubset = new Stack<BitArray>();
		// add first node
		dfaNodes.put(state,0);
		outputTable.add(-1);
		transitionTable.add(null);
		toBuild.push(0);
		toBuildSubset.push(state);
		
		while (!toBuild.isEmpty()) {
			int node = toBuild.pop();
			BitArray subset = toBuildSubset.pop();
			// calculate output count for pattern 
			int k = 0;
			// go through patterns
			for (int i : patternEnds) {
				if (subset.get(i)) ++k;
			}
			outputTable.set(node, k);
			// transition list to be filled in the following
			int[] nodeTransitions = new int[alphabet.size()];
			// for all characters check/add the resulting state
			for (int c=0; c<alphabet.size(); ++c) {
				BitArray targetSubset = new BitArray(subset);
				targetSubset.and(transitions[c]);
				targetSubset.shiftLeft();
				// simulate self-transition for base state
				targetSubset.or(startStates);
				Integer targetNode = dfaNodes.get(targetSubset);
				if (targetNode==null) {
					targetNode = new Integer(outputTable.size());
					if (dfaNodes.size()>=nodeLimit) {
						Log.getInstance().stopTimer("ABORTED: nfa->dfa (subset construction)");
						throw new NodeLimitExceededException();
					}
					dfaNodes.put(targetSubset, targetNode);
					outputTable.add(-1);
					transitionTable.add(null);
					toBuild.push(targetNode);
					toBuildSubset.push(targetSubset);
				}
				nodeTransitions[c]=targetNode;
			}
			transitionTable.set(node, nodeTransitions);
		}
		
		Log.getInstance().stopTimer("nfa->dfa (subset construction)");
		return new CDFA(alphabet, transitionTable, outputTable);		
	}
}
